package com.feiyue.learning.graph;

public class DijkstraTest {

    public static void main(String[] args) {

        // 顶点个数
        int n = 9;

        // 定义二维数组, 存储各个边的距离(0不用) TODO 初始化
        int[][] e = new int[10][10];

        // 用于存放源点到各个顶点的初始路程 TODO 初始化
        int[] dis = new int[10];

        // 定义一维数组用于存放各个顶点到源点的最短路径是否已知, 0-未知, 1-已知
        int[] book = new int[10];
        book[1] = 1;

        // Dijkstra 算法核心代码
        int min;

        // 当前顶点
        int u = 0;
        int inf = 99999; // 该值设为很大表示不可达

        // 循环 n-1, 找到其他顶点到源点最短距离
        for (int i = 1; i <= n - 1; i++) {

            // 找到离顶点1（源点）最近的顶点
            min = inf;

            // 此处查询最近顶点算法可以优化(n->logN)
            for (int j = 2; j <=n; j++) {
                if (book[j] == 0 && dis[j] < min) {
                    min = dis[j];
                    u = j;
                }
            }
            book[u] = 1;

            // 进行顶点 u 相关边的松弛(是否存在顶点 v, dis[v] < dis[u] + e[u][v])
            for (int v = 1; v <= n; v++) {
                if (e[u][v] < inf) {
                    if (dis[v] > dis[u] + e[u][v]) {
                        dis[v] = dis[u] + e[u][v];
                    }
                }
            }
        }
    }
}
